package org.example.leetcode;
import java.util.*;
/**
 * @author: lynn
 * @Descript: 不重复的数组，结果可以取重复的。
 * @link 39,40,46,47 这些题目，不用关系输入值是不是重复的，39和47做法可以v去掉，输入重复的部分；
 * @link 39和40区别在于，39的输出可以重复，40的输出不能重复
 * @link 通用的做法，就是解39,46,47 这种做法，输出是重复的
 * @date: 2021/8/3 22:05
 * @version: 1.0
 */
public class LC39 {
    public static void main(String[] args) {
        LC39 lc=new LC39();
        int[] candidates=new int[]{2,3,6,7};
        int target=7;
        System.out.println(lc.combinationSum(candidates,target));

    }
    //fixme dfs 回溯法 https://www.bilibili.com/video/BV1854y1m7WR?from=search&seid=18402514297705751165
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> list=new ArrayList<>();

        if(candidates==null || candidates.length==0){
            new ArrayList<>(res);
        }
        Arrays.sort(candidates);
        backtrack(candidates,list,res, target,0);
        return new ArrayList<>(res);
    }

    private void backtrack(int[] candidates,List<Integer> list,
                           List<List<Integer>> res,
                           int target,int start) {
        if (target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i=start;i<candidates.length;i++){
            if (candidates[i]>target) break;
            //fixme 控制输出不重复
            if (i>start && candidates[i]==candidates[i-1]) continue;
            list.add(candidates[i]);
            //fixme 这里还是i,代表i可以重复的用
            backtrack(candidates,list,res,target-candidates[i],i);
            list.remove(list.size()-1);

        }
    }

    /**
     *   2,3,6,7
     *
     *   7--2--2
     *   7--3--3
     *   7--2--3--3
     */
}
